#ifndef DLIST_H
#define DLIST_H
#include "Container_t.h"
#include "Link_t.h"
//Dlist_t template class declaration
template<class T> 
class Dlist_t : public Container_t<T>{
public:
	Dlist_t();						
	~Dlist_t();						
	Dlist_t(const Dlist_t& a);
	Dlist_t& operator=(const Dlist_t& a);	
	void Reset();
	T* Next();
	T* Prev();
protected:
	void reset();
	T* next();
	T* prev();
	bool appendAction(const T* elem, const int index) throw (bad_alloc);
	bool removeAction(const T* elem);
	Link_t<T>* getHead();
private:	
	Link_t<T>* first;
	Link_t<T>* last;
	Link_t<T>* pos;	
	Link_t<T>* anchor;
};

template<class T> 
Dlist_t<T>::Dlist_t():first(0),last(first){
	anchor = new Link_t<T>();
	if(anchor == 0){
		throw bad_alloc("Cannot create list");
	}
	anchor->setPrev(last);
	anchor->setNext(first);
	pos = anchor;
}

template<class T> 
Dlist_t<T>::~Dlist_t(){
	removeAll();
	delete(anchor);
}

template<class T> 
Link_t<T>* Dlist_t<T>::getHead(){
	return this->first;
}

template<class T> 
Dlist_t<T>::Dlist_t(const Dlist_t<T> &a):first(0),last(first){
	
	anchor = new Link_t<T>();	
	if(anchor == 0){
		throw bad_alloc("Cannot create list");
	}
	anchor->setPrev(last);
	anchor->setNext(first);
	pos = anchor;
	Link_t<T> *temp = a.first;
	while(temp != 0){
		insert(temp->getData());
		temp = temp->getNext();
	}
	if(a.pos != 0 && a.pos != a.anchor)
		find(*(a.pos)->getData());
	else if(a.pos == a.anchor)
		pos = anchor;
	else
		pos = 0;
}

template<class T> 
Dlist_t<T>& Dlist_t<T>::operator=(const Dlist_t& a){
	if(this != &a){
		removeAll();
		first = last = 0;
		anchor->setPrev(last);
		anchor->setNext(first);
		pos = anchor;
		Link_t<T> *temp = a.first;
		while(temp != 0){
			insert(temp->getData());
			temp = temp->getNext();
		}
		if(a.pos != 0 && a.pos != a.anchor)
			find(*(a.pos)->getData());
		else if(a.pos == a.anchor)
			pos = anchor;
		else
			pos = 0;
		}
	return *this;
}

template<class T> 
void Dlist_t<T>::reset(){
	this->pos = anchor; //TODO: check this ! 
}

template<class T> 
void Dlist_t<T>::Reset(){
	reset();
}

template<class T> 
T* Dlist_t<T>::next(){
	if(pos == 0) return 0;
	if(pos->getNext() == 0) return 0;
	this->pos = pos->getNext();
	return pos->getData();	
}

template<class T> 
T* Dlist_t<T>::Next(){
	return next();
}

template<class T> 
T* Dlist_t<T>::prev(){
	if(pos == 0) return 0;
	if(pos->getPrev() == 0) return 0;	
	this->pos = pos->getPrev();
	return pos->getData();
}

template<class T> 
T* Dlist_t<T>::Prev(){
	return prev();
}

template<class T> 
bool  Dlist_t<T>::appendAction(const T *elem, const int index){
	if(pos == anchor) pos = pos->getNext();
	Link_t<T>* newLink = new Link_t<T>((T*)elem);
	if(newLink == 0){
		throw bad_alloc("cannot allocate memory");
	}
	
	if(count() == 0){ // list is empty
		first = newLink; 		
		last = newLink;  
		anchor->setNext(first);
		anchor->setPrev(last);
		pos = newLink;
		return true;
	}
	
	if(index == count()-1){ //inserting new last element
		newLink->setPrev(this->last);
		this->last->setNext(newLink);
		last = newLink;
		pos = newLink;
		anchor->setNext(first);
		anchor->setPrev(last);
		return true;
	}

	if(index == -1){ //inserting new first element
		newLink->setNext(this->first);
		this->first->setPrev(newLink);
		first = newLink;
		pos = newLink;
		return true;
	}
	Link_t<T>* temp = first;
	for(int i=0;i<index && temp!=0;i++,temp=temp->getNext()){} //find position
	Link_t<T>* nextSaved = temp->getNext();
	Link_t<T>* prevSaved = temp->getPrev();
	newLink->setPrev(temp);
	newLink->setNext(nextSaved);
	temp->setNext(newLink);
	if(nextSaved != 0) 
		nextSaved->setPrev(newLink);
	pos = newLink;
	return true;
}

template<class T> 
bool  Dlist_t<T>::removeAction(const T* elem){	
	if(count()==0) return false; // no elements to remove
	Link_t<T>* removed;
	if(first->getData() == elem){// remove first element
		removed = first;
		first = first->getNext();		
		if(first == 0){ // we removed the only element left in list	  
			last = first;		
		}else{
			first->setPrev(0);
		}
	}
	else if(last->getData() == elem){// remove last element
		removed = last;
		last = last->getPrev();
		if(last == 0){ // we removed the only element left in list	
			first = last;
		}else{
			last->setNext(0);
		}
	}
	else{ 
		if(pos == 0) return false; // element not found
		removed = pos;
		Link_t<T>* savedPrev = pos->getPrev();
		Link_t<T>* savedNext = pos->getNext();
		savedPrev->setNext(savedNext);
		savedNext->setPrev(savedPrev);
	}	
	anchor->setNext(first);
	anchor->setPrev(last);
	
	delete(removed); 
	return true;
}
#endif